package com.hyb.algorithm.data.struct.backtrack;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.List;

/**
 * 39. 组合总和
 * https://leetcode.cn/problems/combination-sum/description/
 * <p>
 * 解题思路
 * https://leetcode.cn/problems/combination-sum/solutions/14697/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
 *
 * @author: ybhu
 * @create: 2023/12/29 08:12
 */
public class CombinationSum2 {

    public static void main(String[] args) {

        int[] candidates = new int[]{2, 3, 6, 7};
        List<List<Integer>> res = new CombinationSum2().combinationSum(candidates, 7);


        System.out.println(JSONObject.toJSON(res));

    }


    private List<List<Integer>> res;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();

        backTrack(candidates, target, 0, list);

        return res;
    }


    public void backTrack(int[] candidates, int target, int start, List<Integer> list) {

        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }

        if (0 == target) {
            res.add(new ArrayList(list));
            return;
        }


        for (int index = start; index < candidates.length; index++) {

            if(target-candidates[index]<0){
                return;
            }

            list.add(candidates[index]);

            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 index，这里非常容易弄错
            backTrack(candidates, target - candidates[index], index , list);

            //状态重置
            list.remove(list.size()-1);
        }
    }
}

